#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=2e5+10;
int a[N];
int q[N];
int sum[N];
int main()
{
	int n,m;
	cin>>n;
	cin>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
	}
	int tail=0;
	int head=0;
	for(int i=1;i<=n;i++)
	{
		sum[i]=sum[i-1];
		if(head==tail)
		{
			q[tail++]=a[i];
			sum[i]++;
			continue;
		}
		if(tail-head==3)
		{
			head++;
		}
		
		if(tail-head==1)
		{
			q[tail++]=a[i];
			sum[i]++;
		}
		else
		{
			if(q[head]<q[head+1])
			{
				sum[i]++;
				q[tail++]=a[i];
			}
			else
			{
				if(a[i]>q[head+1])
				{
					q[tail++]=a[i];
					sum[i]+=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<sum[i]<<' ';
    while(m--)
    {
    	int l,r;
		cin>>l>>r;
		
	}

	return 0;
}

